Статья 3222

Title of the article

On a graph model for reflectometry issues and some algorithms for their solution.
Part 1. Issue statement and approaches to algorithmics 

Authors

Boris F. Mel'nikov, Doctor of physical and mathematical sciences, principal researcher, Federal State Autonomous Research Institution Centre of Information Technologies and Systems for Executive Authorities (building 1, 19 Presnenskiy Val street, Moscow, Russia), E-mail: bormel@mail.ru
Yuliya Yu. Terent'eva, Candidate of engineering sciences, head of the department of analysis and methodology for improving information telecommunication systems, Federal State Autonomous Research Institution Centre of Information Technologies and Systems for Executive Authorities (building 1, 19 Presnenskiy Val street, Moscow, Russia), E-mail: terjul@mail.ru 

Abstract

Background. The relevance of the subject area under consideration is primarily due to the need to minimize the cost of so-called reflectometers, with the existing restriction on the condition of total monitoring of fiber-optic cables. Similar tasks arise when designing and / or upgrading a communication network, and they are especially important in situations where the communication network has a very large dimension. The purpose of the research is to study the possibility of using the method of branches and boundaries in some similar formulations of the problem of reflectometry. Materials and methods. The research uses heuristic algorithms of artificial intelligence and discrete optimization, combined into a single software package, as well as statistical methods for analyzing algorithms. Results. The results are regularities obtained by applying the greedy heuristics and the version of the method of branches and boundaries in solving problems of reflectometry. Conclusions. Algorithms have been proposed describing the improvement of the branch and boundary method by connecting various auxiliary heuristics to it. However, the obtained temporary improvement in the average operating time of this algorithm in the applied problem we have considered, compared to the greedy algorithm, is very small, and this allows us to draw preliminary conclusions that the use of the simplest greedy algorithms is sufficient in reflectometry problems. 

Key words

heuristic algorithms, discrete optimization problems, graph theory models, greedy algorithm, method of brancаhes and boundaries 

Download PDF
For citation:

Mel'nikov B.F., Terent'eva Yu.Yu. On a graph model for reflectometry issues and some algorithms for their solution. Part 1. Issue statement and approaches to algorithmics. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences. 2022;(2):28–39. (In Russ.). doi:10.21685/2072-3040-2022-2-3

 

Дата создания: 16.09.2022 15:19
Дата обновления: 06.10.2022 08:32